package leetcode.backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * @author mazouri
 * @create 2021-09-19 17:28
 */
public class _216_combinationSum3 {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    int k;
    int n;
    int sum = 0;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        this.n = n;
        backtrack(1);
        return res;

    }

    private void backtrack(int start) {
        if (track.size() == k) {
            if (sum == n) res.add(new LinkedList<>(track));
            return;
        }

        //剪枝
        if (sum > n) return;

        for (int i = start; i <= 9; i++) {
            track.add(i);
            sum += i;
            backtrack(i + 1);
            sum -= i;
            track.removeLast();
        }
    }
}
